package code;

import java.util.Arrays;

public class dp {
	//不需要装满
	public int dp1(int[] w,int[] v,int capacity) {
		 int n=w.length,V=v.length;
		 int[][] dp=new int[n+1][capacity+1];
		 
		 for(int i=1;i<=n;i++) {
			 for(int j=0;j<=capacity;j++) {
				 dp[i][j]=dp[i-1][j];
				 if(j>v[i-1]) {
					 dp[i][j]=Math.max(dp[i][j], dp[i][j-v[i-1]+w[i-1]]);
				 }
			 }
		 }
		 return dp[n][capacity];
	}
	
	
	//需要装满
	public int dp2(int[] w,int[] v,int capacity) {
		int n=w.length,V=v.length;
		 int[][] dp=new int[n+1][capacity+1];
		 for(int i=0;i<n=n;i++) {
			 Arrays.fill(dp[i], -1);  //初始值为-1，表示无法拼成
		 }
		 dp[0][0]=0; //0个物品可以拼0体积
		 for(int i=1;i<=n;i++) {
			 for(int j=0;j<=capacity;j++) {
				 dp[i][j]=dp[i-1][j];
				 if(j>v[i-1]&&dp[i][j-v[i-1]]+w[i-1]!=-1) {
					 dp[i][j]=Math.max(dp[i][j], dp[i][j-v[i-1]+w[i-1]]);
				 }
			 }
		 }
		 return dp[n][capacity]==-1?0:dp[n][capacity];
	}
	
}
